class Solution {
    public int mySqrt(int x) {
        // i * i <= x
        long left = 0;
        long right = x;
        long mid = 0;
        while (left < right) {
            mid = (left + right + 1) >> 1;
            if (mid * mid <= x) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return (int)right;
    }
}
